package array;

/**
 * leet-code(169) 多数元素 摩尔投票法
 *
 * @author Ringo
 * @date 2021/9/2 17:14
 */
public class MajorityElement {

    public static void main(String[] args) {
        int[] nums1 = {3, 2, 3};
        System.out.println(majorityElement(nums1));
        int[] nums2 = {2, 2, 1, 1, 1, 2, 2};
        System.out.println(majorityElement(nums2));
    }

    public static int majorityElement(int[] nums) {
        if (nums == null || nums.length == 0)
            return -1;

        int count = 0;                  // 计数器
        Integer candidate = null;       // 候选结果

        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += candidate == num ? 1 : -1;
        }
        return candidate;
    }
}
